package acwing._1_1AlgorithmBasic;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing.Learning.AlgorithmTemplate
 * @File : _2_3KMP.java
 * @Author : WangRuoyu
 * @Date 2023/3/12 10:24
 */
public class _2_3KMP {
    // KMP算法
    public static int maxfixKMP(String s) {
        f1:
        for (int i = s.length() - 1; i >= 0; --i) {
            for (int j = 0, k = s.length() - i; j < i; ++j, ++k) {
                if (s.charAt(j) != s.charAt(k)) {
                    continue f1;
                }
            }
            return i;
        }
        return 0;
    }

    public static int[] nextKMP(String s) { // 求next数组
        int[] next = new int[s.length()];
        next[0] = 0;
        int maxfix;
        for (int i = 1; i < s.length(); ++i) {
            next[i] = maxfixKMP(s.substring(0, i)) + 1;
        }

//        // 对next进行优化
//        for (int i = 1; i < next.length; ++i) {
//            while (next[i] != 0 && s.charAt(i) == s.charAt(next[i] - 1)) {
//                next[i] = next[next[i] - 1];
//            }
//        }
        return next;
    }

    public static void KMP(String p, String s) {
        int res = -1;
        int[] next = nextKMP(s);

        for (int i = 0, j = 0; i < p.length(); ++j, ++i) {
            if (p.charAt(i) != s.charAt(j)) {
                while (j != -1 && s.charAt(j) != p.charAt(i)) {
                    j = next[j] - 1;
                }
            } else {
                if (j == s.length() - 1) {
                    System.out.println(i - j + " " + i);
                }
            }
        }
    }
}

